\chapter{Teknik Greedy}


\ifthenelse{\boolean{adaTIU}}{
	\begin{footnotesize}
	  \begin{description}
	  \item[Tujuan Pembelajaran]:
	  \begin{itemize}
			\item Memberikan penjelasan mengenai algoritma yang menggunakan teknik Greedy dan masalah yang dapat diselesaikan dengan teknik tersebut
			\item Memberikan penjelasan mengenai algoritma Minimum Spanning Tree
			\item Memberikan penjelasan mengenai algoritma shortest path Dijkstra
			\item Memberikan penjelasan mengenai Pengkodean Huffman
		\end{itemize}
		\item[Setelah menyelesaikan modul ini mahasiswa diharapkan dapat]:
		\begin{itemize}
			\item Menjelaskan masalah Minimum Spanning Tree
			\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas MST Prim
			\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas MST Kruskal
			\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas Shortest Path Dijkstra
			\item Menjelaskan masalah Pengkodean Huffman
			\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas Pengkodean Huffman
		\end{itemize}
		\item[Kata kunci]:
		\begin{itemize}
		  \item Minimum Spanning Tree, MST Prim, MST Kruskal, Shortest path Dijkstra, Pengkodean Huffman
		\end{itemize}
		\end{description}
	\end{footnotesize}
}


\section{Pendahuluan}

Bab ini membahas kelompok masalah yang dipecahkan dengan menggunakan \index{greedy technique@\emph{greedy technique}} teknik \emph{greedy}. Masalah-masalah yang termasuk ke dalam kelompok ini biasanya adalah masalah-masalah \index{optimal problem@\emph{optimal problem}} pencarian solusi optimal. Sesuai dengan namanya, \emph{greedy} dapat kita terjemahkan secara harfiah sebagai "serakah" atau "rakus". Teknik ini secara bertahap mencari solusi akhir melalui serangkaian pencarian sub-solusi. Dalam hal ini teknik \emph{greedy} memiliki kemiripan dengan teknik \emph{decrease and conquer} pada Bab~\ref{ch:decrease-and-conquer}. Perbedaannya terletak pada pilihan sub-solusi yang diambil. Pada teknik \emph{greedy}, secara 'serakah' teknik ini mengambil sub-solusi yang 'terbaik'.

Perlu diperhatikan bahwa pencarian sub-solusi terbaik tergantung dari sifat masalah yang sedang dihadapi. Ada kalanya sub-solusi terbaik kita ambil berdasarkan nilai minimum, dalam kasus yang lain kita dapat mengambil sub-solusi berdasarkan nilai maksimum. Perlu diperhatikan pula bahwa kadang-kadang solusi akhir yang dihasilkan dari pemilihan dengan teknik \emph{greedy} bukan merupakan solusi yang paling optimal. Hal ini disebabkan karena algoritma greedy akan langsung menganggap pilihan terbaik dalam tahap pencarian sub-solusi sebagai bagian dari solusi permasalahan akhir tanpa mengecek keberadaan kemungkinan-kemungkinan lain yang mungkin saja lebih tepat menjadi solusi akhir yang paling optimal. Namun demikian dalam banyak permasalahan, teknik \emph{greedy} dapat memberikan solusi akhir terbaik. Salah satu hal yang merupakan kelebihan dari teknik ini adalah singkatnya waktu yang diperlukan dalam menyelesaikan masalah.

Bab ini mengemukakan beberapa contoh permasalahan yang dapat diselesaikan dengan algoritme yang menggunakan teknik \emph{greedy}, yaitu pencarian \emph{minimum spanning tree} (MST), baik dengan metoda Kruskal maupun Prim, pencarian jarak terpendek dari satu verteks ke verteks lainnya yang ada dalam sebuah graf (\emph{shortest path}) serta pengkodean Huffman. Masalah \emph{minimum spanning tree} dan \emph{shortest-path} menggunakan struktur data graf yang lebih detil dibahas pada Subbab~\ref{sect:graf}.


\section{Minimum Spanning Tree} \label{sect:mst}

\index{minimum spanning tree@\emph{Minimum Spanning Tree}} \index{mst@MST} \emph{Minimum Spanning Tree} (MST) merupakan salah satu persoalan optimasi yang sering ditemui dalam kehidupan sehari-hari. Sebagai contoh, perancangan jalur transmisi listrik yang dapat menghubungkan beberapa kota dengan biaya minimal dapat menggunakan metode pencarian MST. Tujuan dari perancangan tersebut adalah bagaimana meminimalkan panjang kabel yang menghubungkan setiap kota dengan kota lain. Semakin pendek panjang kabel yang terentang, maka akan semakin murah biaya yang diperlukan untuk menghubungkan kota-kota tersebut dalam sebuah jaringan transmisi listrik.

Banyak masalah lain dapat dimodelkan dengan MST, tidak hanya terbatas pada pencarian panjang kabel paling pendek seperti contoh di atas. Beberapa masalah lain di antaranya lintasan terpendek antara satu kota dengan kota lainnya di sebuah negara, jarak terpendek lintasan sirkuit pada \emph{Printed Circuit Board} yang antara lain bisa ditemukan pada \emph{motherboard} komputer.

Contoh permasalahan di atas dapat dimodelkan dalam bentuk \index{graf!berbobot} \index{graph@\emph{graph}!weighted@\emph{weighted}} graf berbobot (\emph{weighted graph}), di mana setiap kota merupakan verteks dan jalur transmisi yang menghubungkan antar kota adalah edge. Setiap edge memiliki bobot atau \emph{weight} yang menyatakan biaya yang diperlukan untuk merentangkan kabel listrik dari satu kota ke kota yang lain. Perhatikan bahwa dalam masalah ini kita tidak memperdulikan jalur yang dipilih untuk menghubungkan seluruh kota, yang menjadi inti masalahnya adalah bagaimana mencari panjang kabel terpendek. Bila seluruh kemungkinan jalur transmisi dan biaya pembangunan setiap jalur tersebut diketahui, maka jalur transmisi yang dapat menghubungkan seluruh kota dengan biaya minimal tidak lain adalah \emph{minimum spanning tree} dari model graf tersebut.

MST suatu graf dapat dipandang sebagai himpunan edge, yang menghubungkan semua verteks pada graf dengan bentuk \emph{tree} di mana jumlah total \emph{weight} dari seluruh edge yang membentuk \emph{tree} bernilai minimum. Dengan pengertian tersebut suatu MST dapat dibangun mulai dari suatu himpunan kosong. Selanjutnya pada himpunan tersebut ditambahkan anggota baru di antara edge yang memenuhi syarat \index{safe edge@\emph{safe edge}} (\emph{safe edge}), yaitu yang mempunyai \emph{weight} terkecil. Karena MST merupakan suatu \emph{tree}, yang didefinisikan sebagai sebuah \emph{connected graph} tanpa \emph{cycle}, maka \emph{safe edge} yang diambil tidak boleh menyebabkan munculnya \emph{cycle}. Jika \emph{safe edge} menghasilkan \emph{cycle}, maka \emph{safe edge} tersebut pasti bukan merupakan bagian dari MST akhir dan dapat diabaikan.

Algoritma dasar tersebut dapat dituliskan seperti diperlihatkan pada Algoritme~\ref{alg:generic-mst}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{Generik MST} $(G)$
	\COMMENT Inisialisasi $F$ sebagai himpunan kosong dari edge
	\STATE $F \leftarrow \emptyset$
	\WHILE{$F$ belum membentuk MST}
		\STATE Cari edge $(u,v)$ yang memenuhi syarat untuk digabung dengan $F$
		\STATE $F \leftarrow F \cup (u,v)$
	\ENDWHILE
	\STATE return $F$
\end{algorithmic}
\caption{Algoritme MST generik.} \label{alg:generic-mst}
\end{algorithm}

\subsection{Algoritma Kruskal}

Dengan menggunakan prinsip dari Generik MST, Algoritme~\ref{alg:generic-mst} \index{kruskal@Kruskal} Kruskal membangun MST dengan cara memilih di antara edge yang ada mulai dari yang edge dengan bobot terkecil. Perhatikan Algoritme~\ref{alg:kruskal}. Langkah pertama yang dilakukan adalah mengurutkan semua edge di dalam graf secara terurut berdasarkan bobotnya secara \emph{ascending}.

Secara bertahap algoritme Kruskal mengambil satu per satu edge dari daftar yang sudah terurut tadi dan dimasukkan ke dalam bagian dari MST. Setiap kali sebuah edge diambil, perlu diperiksa terlebih dahulu apakah jika edge tersebut diambil akan membentuk \emph{cycle}. Jika tidak membentuk \emph{cycle}, maka edge tersebut diambil sebagai bagian dari MST. Proses ini dilakukan terus hingga semua edge dalam daftar terurut habis diperiksa apakah memang merupakan bagian dari MST atau bukan. Perhatikan bahwa dengan mengurutkan edge dalam graf secara \emph{ascending}, secara tidak langsung algoritme Kruskal selalu mengambil \emph{safe edge} dalam setiap iterasinya.

Pengecekan adanya \emph{cycle} yang terjadi dapat dilakukan dengan memeriksa verteks yang \emph{incident} dengan edge yang sedang diperiksa. Setiap edge pasti ber-\emph{incident} dengan dua buah verteks. Ketika sebuah edge diperiksa apakah dia merupakan bagian dari MST atau bukan, kita perlu memeriksa apakah edge tersebut akan membentuk \emph{cycle}. \emph{Cycle} akan terbentuk apabila kedua verteks yang ber-\emph{incident} dengan edge tersebut sudah merupakan bagian dari MST yang sudah terbentuk. Jika salah satu verteks bukan merupakan bagian dari MST yang sudah terbentuk, maka edge tersebut pasti merupakan bagian dari MST berikutnya. Jika kedua verteks sudah menjadi bagian dari MST yang terbentuk, berarti edge tersebut dapat diabaikan karena pasti akan membentuk \emph{cycle} di dalam MST yang sudah ada.

Dalam Algoritma~\ref{alg:kruskal}, baris~\ref{alg:kruskal:initialize} mengurutkan \emph{edge} secara \emph{ascending} berdasarkan bobotnya. Selanjutnya pada baris~\ref{alg:kruskal:add-to-mst} pasangan verteks yang \emph{incident} dengan \emph{edge} pertama dari himpunan $L$ dimasukkan ke dalam himpunan $B$. Himpunan ini digunakan untuk memeriksa adanya \emph{cycle} atau tidak ketika sebuah edge baru akan ditambahkan ke dalam MST yang dibangun. Pengecekan terjadinya \emph{cycle} dilakukan pada baris~\ref{alg:kruskal:check-cycle} dengan memeriksa apakah verteks-verteks $u$ dan $v$ yang ber-\emph{incident} dengan \emph{edge} $f$ berada dalam himpunan $B$ atau tidak. Jika kedua verteks tersebut bukan anggota $B$, maka edge $f$ ditambahkan ke dalam himpunan $A$.

Ketika algoritma tersebut berakhir, himpunan $A$ akan berisi \emph{edges} dari graf $G$ yang menyusun MST yang dicari.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{MSTKruskal} $(G)$
	\STATE \COMMENT $G$ adalah graf yang akan dicari MST-nya.
	\STATE $L \leftarrow e \in \mathrm{Edge}(G)$ terurut secara ascending berdasarkan bobot. \label{alg:kruskal:initialize}
	\STATE $A \leftarrow \emptyset$
	\STATE $B \leftarrow \emptyset$
  \STATE $f \leftarrow$ remove-first-element$(L)$
  \STATE $A \leftarrow A \cup f$
  \STATE $u,v \leftarrow $ verteks yang \emph{incident} dengan $f$
  \STATE $B \leftarrow B \cup u \cup v$ \label{alg:kruskal:add-to-mst}
	\WHILE{$L \neq \emptyset$}
	  \STATE $f \leftarrow$ remove-first-element$(L)$
	  \STATE $u,v \leftarrow $ verteks yang \emph{incident} dengan $f$
	  \IF{$u \notin B$ OR $v \notin B$} \label{alg:kruskal:check-cycle}
	    \STATE $A \leftarrow A \cup f$
	    \STATE $B \leftarrow B \cup u \cup v$
	  \ENDIF \label{alg:kruskal:check-cycle-end}
	\ENDWHILE
\end{algorithmic}
\caption{Algoritme Kruskal.} \label{alg:kruskal}
\end{algorithm}

\subsection{Algoritma Prim}

\index{prim@Prim} Algoritme Prim membangun MST dimulai dari satu verteks yang ditentukan, disebut sebagai \index{vertex@\emph{vertex}!source@\emph{source}} \emph{source vertex}. Pemilihan \emph{source vertex} dapat dilakukan secara bebas, tanpa ada batasan verteks yang mana yang harus dijadikan sebagai titik awal. \emph{Source vertex} ini digunakan sebagai informasi untuk membentuk sebuah konfigurasi yang disebut \emph{cut}.

\index{graf!cut@\emph{cut}} \emph{Cut} dari sebuah graf adalah konfigurasi di mana himpunan verteks dari graf tersebut dipisahkan atau dipotong ke dalam dua himpunan terpisah. Jika sebuah graf memiliki himpunan verteks $V = \{v_1, v_2, \ldots, v_n \}$, maka \emph{cut} dapat dibentuk dengan membuat dua sub-himpunan $A \subseteq V$ dan $B \subseteq V$ di mana $A \cup B = V$ dan $A \cap B = \emptyset$. Perlu diperhatikan bahwa pemilihan anggota himpunan $A$ dan $B$ dapat dilakukan secara bebas, yang penting irisan kedua himpunan tersebut haruslah himpunan kosong, dan gabungan kedua himpunan itu harus kembali membentuk himpunan awal verteks $V$.

Dari sebuah konfigurasi \emph{cut}, kita dapat membentuk himpunan \index{crossing edge@\emph{crossing edge}} \index{edge@\emph{edge}!crossing@\emph{crossing}} \emph{crossing edge} $CE$. Himpunan ini didefinisikan sebagai \emph{edges} yang menghubungkan verteks-verteks di $A$ dengan verteks-verteks di $B$. \emph{Edges} yang menghubungkan verteks-verteks di dalam himpunan $A$ bukan dikatakan sebagai \emph{crossing edge}, demikian pula semua edge yang menghubungkan verteks-verteks anggota himpunan $B$. Anggota himpunan \emph{crossing edge} yang memiliki bobot terkecil disebut sebagai \index{light edge@\emph{light edge}} \index{edge@\emph{edge}!light@\emph{light}} \emph{light edge}.

Algoritme Prim membangun MST berawal dari \emph{source vertex} $v_s$ dengan membentuk sebuah \emph{cut}:
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaauaabaqacmaaaeaacaWGbbaabaGaeyypa0
% dabaGaamODamaaBaaaleaacaWGZbaabeaaaOqaaiaadkeaaeaacqGH
% 9aqpaeaacaWGwbGaeyOeI0Iaamyqaaaaaaa!3A06!
\[
\begin{array}{*{20}c}
   A \hfill &  =  \hfill & { \{ v_s \} } \hfill  \\
   B \hfill &  =  \hfill & {V - A} \hfill  \\
\end{array}
\]
% MathType!End!2!1!
Berdasarkan konfigurasi \emph{cut} ini, kita cari \emph{light edge} yang menghubungkan $v_s$ dengan sebuah verteks di himpunan $B$, $v_{\mathrm{next}}$. \emph{Light edge} ini pasti merupakan bagian dari MST yang kita cari, sehingga edge tersebut kita masukkan ke dalam himpunan edge yang membentuk MST. Karena edge ini menghubungkan $v_s$ dengan sebuah verteks di $B$, maka kemudian kita membentuk sebuah konfigurasi \emph{cut} yang baru, di mana:
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaauaabaqacmaaaeaacaWGbbaabaGaeyypa0
% dabaGaamODamaaBaaaleaacaWGZbaabeaaaOqaaiaadkeaaeaacqGH
% 9aqpaeaacaWGwbGaeyOeI0Iaamyqaaaaaaa!3A06!
\[
\begin{array}{*{20}c}
   A \hfill &  =  \hfill & { \{ v_s \} } \cup \{ v_{\mathrm{next}} \} \hfill  \\
   B \hfill &  =  \hfill & {V - A} \hfill  \\
\end{array}
\]
% MathType!End!2!1!

Perhatikan bahwa pengambilan \emph{light edge} merupakan pendekatan \emph{greedy}, di mana kita selalu mengambil edge dengan pilihan terbaik.

Iterasi ini kita lakukan secara berulang hingga pada akhirnya kita dapatkan sebuah konfigurasi \emph{cut}:
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaauaabaqacmaaaeaacaWGbbaabaGaeyypa0
% dabaGaamODamaaBaaaleaacaWGZbaabeaaaOqaaiaadkeaaeaacqGH
% 9aqpaeaacaWGwbGaeyOeI0Iaamyqaaaaaaa!3A06!
\[
\begin{array}{*{20}c}
   A \hfill &  =  \hfill & {V} \hfill  \\
   B \hfill &  =  \hfill & \emptyset \hfill  \\
\end{array}
\]
% MathType!End!2!1!
Ketika himpunan $B$ sudah kosong, berarti seluruh verteks dalam graf $G$ sudah terentang atau \emph{spanned} oleh \emph{light edges} yang ada dalam $G$.

Algoritme~\ref{alg:prim} memberikan langkah-langkah untuk membuat MST dengan cara Prim. Pemilihan \emph{source vertex} pada baris~\ref{alg:prim:source-vertex} tidak harus dilakukan secara acak. Jika tidak ada panduan yang jelas, memilih \emph{source vertex} berdasarkan urutan pertama nama verteks juga dapat dilakukan, misalnya memilih verteks berlabel $u$ pada graf dengan himpunan verteks $V = \{u, v, w, x, y\}$. Pengecekan kondisi pada iterasi di baris~\ref{alg:prim:main-loop} juga dapat dilakukan dengan memeriksa apakah himpunan $B$ sudah kosong atau belum. Pada akhir algoritma, himpunan $mst$ akan berisi seluruh \emph{light edges} yang menyusun MST yang dicari.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{MSTPrim} $(G)$
	\STATE Pilih $v_s \in V(G)$ secara acak sebagai \emph{source vertex} \label{alg:prim:source-vertex}
	\STATE $mst \leftarrow \emptyset$
	\STATE $A \leftarrow \{ v_s \}$
	\STATE $B \leftarrow V - A$
	\WHILE{$A \neq V$} \label{alg:prim:main-loop}
	  \STATE Pilih \emph{light edge} $e$ yang menghubungkan $v_{a} \in A$ dengan $v_{\mathrm{next}} \in B$
	  \STATE $mst \leftarrow mst \cup \{ e \}$
	  \STATE $A \leftarrow A \cup \{ v_{\mathrm{next}} \}$
	  \STATE $B \leftarrow V - A$
	\ENDWHILE
	\STATE return $mst$
\end{algorithmic}
\caption{Algoritme Prim.} \label{alg:prim}
\end{algorithm}


\section{Algoritme Dijkstra} \label{algoritme-dijkstra} \label{sect:algoritme-dijkstra}

Dalam suatu graf berbobot, seringkali suatu verteks dapat dicapai dari verteks lain melalui lebih dari satu cara. Dalam hal tersebut seringkali harus dicari lintasan mana yang memiliki bobot terkecil di antara banyak pilihan lintasan. Permasalahan seperti ini dikenal sebagai permasalahan untuk mencari jarak \index{lintasan terpendek} lintasan terpendek atau \index{shortest path@\emph{shortest path}} \emph{shortest path}.

Ada beberapa algoritme yang menjawab masalah lintasan terpendek ini. Salah satunya adalah \index{algoritme!dijkstra@Dijkstra} algoritme Dijkstra. Algoritme ini tergolong ke dalam kelompok algoritme yang memecahkan masalah \index{shortest path@\emph{shortest path}!single source@\emph{single source}} \emph{single source shortest path}. Kelompok masalah ini mencari lintasan terpendek dari \textbf{satu} verteks ke verteks-verteks yang lain di dalam sebuah graf.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{Relax} $(i, j, k)$
	\IF{$d_{j} > d_{k} + d(k,j)$}
		\STATE $d_{j} \leftarrow d_{k} + d(k,j)$
		\STATE $\pi_{j} \leftarrow k$ \label{alg:relax:set-parent}
	\ENDIF
\end{algorithmic}
\caption{Algoritme relaksasi.} \label{alg:relax}
\end{algorithm}

Algoritme Dijkstra mencari lintasan terpendek antara dua buah verteks dengan menggunakan \index{prinsip relaksasi} prinsip relaksasi. Perhatikan Algoritma~\ref{alg:relax} dan Gambar~\ref{fig:prinsip-relaksasi-b}. Misalkan diketahui verteks $j$ dapat dicapai dari verteks $i$ dengan panjang lintasan atau \emph{distance} $d_j = d(i,j)$. Lintasan dari verteks $i$ ke $j$ tidaklah unik, bisa jadi terdapat kemungkinan lintasan lain yang dapat ditempuh untuk mencapai verteks $j$ dari $i$, katakanlah melalui verteks $k$. Prinsip relaksasi menyarankan kepada kita untuk memeriksa lintasan $i-k-j$, karena lintasan ini mungkin memiliki panjang lintasan yang lebih pendek daripada lintasan $i-j$ secara langsung. Bobot yang diperlukan untuk mencapai verteks $j$ melalui verteks $k$ adalah $d_{k} + d(k,j)$ di mana $d(k,j)$ adalah \emph{distance} yang diperlukan untuk mencapai verteks $j$ dari $k$. Jika ternyata nilai $d_j < d_k + d(k,j)$, maka pada saat itu kita tahu bahwa jarak terpendek untuk mencapai $j$ dari $i$ adalah melalui verteks $k$.

Karena verteks $j$ dapat dicapai dari $i$ dengan lebih dulu mengunjungi verteks $k$, maka kita catat \emph{parent} dari verteks $j$ adalah verteks $k$. Hal ini dilakukan pada baris~\ref{alg:relax:set-parent} dalam Algoritme~\ref{alg:relax}. Informasi \emph{parent} ini bisa kita gunakan untuk menelusuri lintasan terpendek untuk mencapai verteks $j$.

\begin{figure}
	\begin{center}
	\resizebox*{0.3\textwidth}{!}{
		\includegraphics{relaksasi}
	}
	\caption{\index{prinsip relaksasi} Prinsip relaksasi.} \label{fig:prinsip-relaksasi-b}
	\end{center}
\end{figure}

Algoritme Dijkstra dimulai dengan mengasumsikan bahwa verteks-verteks selain verteks awal (\emph{source vertex}) tidak dapat dicapai dari verteks awal. Asumsi ini dinyatakan dengan memberi nilai jarak pada verteks-verteks tersebut dengan sebuah nilai tak-hingga, $\infty$. Untuk mengetahui verteks-verteks mana saja yang membangun lintasan paling pendek, algoritme Dijkstra juga mencatat \emph{parent} dari sebuah verteks. \emph{Parent} $\pi_{v}$ menunjukkan sebuah verteks $u$ di mana terdapat lintasan dari \emph{source vertex} $s$ melalui satu atau beberapa verteks lain hingga mencapai $u$ kemudian dilanjutkan melalui satu edge ke $u$. Jadi, verteks $u$ adalah pendahulu atau \emph{predecessor} atau \emph{parent} dari verteks $v$. Dengan kata lain $\pi_v = u$. Dalam tahap inisialisasi, $\pi_{v}$ untuk setiap verteks $v$ selain $s$ dinyatakan sebagai $\mathtt{NIL}$.

Inisialisasi tersebut dituliskan dalam bentuk satu algoritma seperti Algoritme~\ref{alg:init-dijkstra}. Algoritma ini memberi nilai $d_{v}$ dengan $\infty$ dan $\pi_v$ dengan $\mathtt{NIL}$ untuk setiap verteks $v$ selain $s$. Perhatikan bahwa dalam algoritma tersebut \textbf{seluruh} verteks dalam graf $G$ diinisialisasi, kecuali verteks $s$ yang diberi nilai awal $0$ pada baris~\ref{alg:init-dijkstra:distance-s}. Karena dalam \emph{looping} utama baris~\ref{alg:init-dijkstra:main-loop} hingga~\ref{alg:init-dijkstra:main-loop-end} semua verteks diberi \emph{parent} $\mathtt{NIL}$, otomatis \emph{parent} verteks $s$ juga $\mathtt{NIL}$.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{InitDijkstra} ( G, s )
	\STATE \COMMENT{Menginisialisasi graf $G$ untuk algoritme Dijkstra, dengan $s$ sebagai \emph{source vertex}.}
	\FOR{setiap verteks $v \in V(G)$} \label{alg:init-dijkstra:main-loop}
	  \STATE $d_{v} \leftarrow \infty$
	  \STATE $\pi_{v} \leftarrow \mathtt{NIL}$
	\ENDFOR \label{alg:init-dijkstra:main-loop-end}
	\STATE $s \leftarrow 0$ \label{alg:init-dijkstra:distance-s}
\end{algorithmic}
\caption{Algoritme inisialisasi Dijkstra.} \label{alg:init-dijkstra}
\end{algorithm}

Algoritme~\ref{alg:dijkstra} menunjukkan langkah-langkah yang dilakukan untuk mencari \emph{shortest path} dalam graf $G$ dengan verteks awal $s$. Algoritma ini menggunakan himpunan $S$ yang berisi verteks-verteks yang sudah diproses dan sebuah \index{priority queue@\emph{priority queue}} \emph{priority queue} $P$ yang menyimpan verteks-verteks yang masih belum diproses. Verteks-verteks dalam $P$ disusun berdasarkan jarak masing-masing verteks ke verteks terdekat di $S$. Dengan kata lain verteks pada urutan terdepan di $P$ adalah verteks yang memiliki \emph{distance} terdekat.

Selama algoritme Dijkstra berjalan, anggota $S$ akan bertambah sementara anggota $P$ akan berkurang. Proses akan selesai ketika $P$ sudah kosong.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{Dijkstra} $(G, s)$
	\STATE \COMMENT{Menerapkan algoritme Dijkstra pada graf $G$ dengan \emph{source vertex} $s$.}
	\STATE \textsc{InitDijkstra} $( G, s )$
	\STATE $S \leftarrow \emptyset$
	\STATE \COMMENT{Buat \emph{priority queue} $P$ dari semua verteks di $G$.}
	\STATE $P \leftarrow V - {s}$
	\WHILE{$P$ tidak kosong}
		\STATE Atur kembali P sebagai priority queue
		\STATE $u \leftarrow \mathrm{ExtractMin}(P)$
		\STATE $S \leftarrow S \cup u$
		\FOR{setiap verteks $v$ yang adjacent dengan $u$}
			\STATE \textsc{Relax} $(u, v, w)$
		\ENDFOR
	\ENDWHILE
\end{algorithmic}
\caption{Algoritme Dijkstra.} \label{alg:dijkstra}
\end{algorithm}

\begin{figure}
	\begin{center}
		\resizebox*{0.5\textwidth}{!}{
			\includegraphics{dijkstra-g1}
		}
		\caption{Graf untuk contoh algoritme Dijkstra~\cite{edmonds-algorithm}.} \label{fig:graf-dijkstra-g1}
	\end{center}
\end{figure}

Karena pada akhirnya S akan beranggotakan seluruh vertex pada graph G yang terhubung dengan vertex asal s, maka dalam implementasi S dapat dibuat sebagai bagian dari struktur data graph G.

Algoritma Dijkstra merupakan algoritma untuk mencari jarak lintasan terpendek dari suatu vertex ke vertex lainnya pada suatu graph yang semua edgenya mempunyai nilai weight tidak negatif.


\section{Pengkodean Huffman}

Dalam suatu sistem komputer pada umumnya setiap karakter dikodekan dengan jumlah bit yang sama. ASCII mengkodekan setiap karakter dengan 8 bit, oleh karena itu maka untuk suatu file ASCII yang terdiri atas 100 000 karakter diperlukan 800 000 bit tempat penyimpanan data. Bila saja frekuensi dari setiap karakter tersebut tidak sama, maka kebutuhan jumlah tempat penyimpanan data dapat diperkecil dengan cara memberikan kode dengan jumlah bit lebih pendek untuk karakter yang sangat sering muncul. 

Dengan cara berfikir tersebut Huffman membuat algoritma untuk mengkodekan sejumlah karakter dengan jumlah bit sesedikit mungkin. Adapun cara pengkodean Huffman ini dilakukan dengan cara berikut:
\begin{itemize}
\item Atur karakter urut berdasarkan frekuensi terkecil kemunculannya.
\item Buat forest yang terdiri atas tree yang dari masing-masing terdiri atas sebuah node yang merupakan representasi karakter tersebut.
\item Gabungkan tree dari dua node dengan frekuensi terkecil, sehingga terbentuk binary tree dengan root baru dengan frekuensi yang merupakan penjumlahan frekuensi dari node yang digabungkan, anak kiri adalah node yang mempunyai frekuensi lebih kecil dan anak kanan adalah node yang mempunyai frekuensi lebih besar.
\item Urutkan kembali forest tersebut berdasarkan frekuensi terkecil dari root setiap tree.
\item Lakukan kembali penggabungan dua buah tree dengan frekuensi terkecil.
\item Demikian seterusnya hingga terbentuk sebuah binary tree yang disebut Huffman Tree.
\end{itemize}

Untuk dapat membandingkan jumlah bit yang dipergunakan dalam pengkodean biasa dengan pengkodean Huffman perhatikan contoh dibawah ini:

Misal terdapat 8 karakter A, B, C, D, E, F, G dan blank, masing-masing dengan frekuensi sebagai berikut:
\begin{center}
	\small{
		\begin{tabular}{|c|c|c|||c|c|c|}
			\hline
				Karakter & Frekuensi (\%) & Kode ASCII & Karakter & Frekuensi (\%) & Kode ASCII \\
			\hline
				A & 12 & $0100 \ 0001$ & E & 30 & $0100 \ 0101$ \\
				B & 3 & $0100 \ 0010$ & F & 10 & $0100 \ 0110$ \\
				C & 20 & $0100 \ 0011$ & G & 6 & $0100 \ 0111$ \\
				D & 4 & $0100 \ 0100$ & $\sqcup$ & 15 & $0010 \ 0000$ \\
			\hline
		\end{tabular}
	}
\end{center}
Setiap huruf dalam data tersebut direpresentasikan sebagai sebuah verteks dengan label nama huruf dan frekuensi kemunculannya.

Algoritme Huffman membangun sebuah \emph{Huffman tree} dengan cara membangun serangkaian \emph{Huffman forest}. \emph{Huffman forest} yang pertama dibuat dengan menyusun verteks-verteks huruf tadi berurut berdasarkan frekuensi kemunculannya secara \emph{ascending}, seperti ditunjukkan dalam Gambar~\ref{subfig:huffman-forest-1}. Secara iteratif algoritme Huffman mengambil pasangan verteks atau pasangan \emph{tree} dari \emph{forest} yang memiliki nilai gabungan terkecil. Seperti ditunjukkan dalam Gambar~\ref{subfig:huffman-forest-2}, kita ambil verteks $B$ dan $D$ untuk digabung menjadi sebuah \emph{tree} baru dengan bobot gabungan dari kedua verteks tersebut, yaitu $7$. \emph{Tree} yang baru terbentuk ini kita letakkan pada urutan yang sesuai pada \emph{forest} yang masih tersisa, dalam contoh ini kita letakkan di antara verteks $G$ dan $F$.

\begin{figure}
	\begin{center}
		\subfigure[Langkah 1]{\resizebox*{0.9\textwidth}{!}{\includegraphics{huffman-forest-1}}} \label{subfig:huffman-forest-1}
		\subfigure[Langkah 2]{\resizebox*{0.9\textwidth}{!}{\includegraphics{huffman-forest-2}}} \label{subfig:huffman-forest-2}
		\subfigure[Langkah 3]{\resizebox*{0.9\textwidth}{!}{\includegraphics{huffman-forest-3}}} \label{subfig:huffman-forest-3}
	\end{center}
	\caption{Cara Pembentukan Huffman Tree berdasarkan data pada tabel.} \label{fig:build-huffman-tree}
\end{figure}

\begin{figure}
	\begin{center}
	  \resizebox*{0.9\textwidth}{!}{
			\includegraphics{huffman-forest-7}
		}
	\end{center}
	\caption{Huffman Tree yang dihasilkan dari proses pada Gambar~\ref{fig:build-huffman-tree}.} \label{fig:huffman-tree}
\end{figure}

Proses pengambilan pasangan verteks atau \emph{tree} seperti ini kita lakukan secara berulang hingga pada akhirnya kita menggabungkan seluruh verteks dalam satu \emph{single tree}, seperti dalam Gambar~\ref{fig:huffman-tree}. \emph{Tree} ini kita gunakan untuk membangun kode Huffman yang diperlukan. Caranya adalah dengan memberi label untuk setiap edge pada \emph{tree} dengan perjanjian bahwa edge untuk anak kiri diberi label $0$ sedangkan edge untuk anak kanan diberi label $1$. Untuk mengetahui kode Huffman dari setiap huruf, kita dapat mengambil jalur mulai dari \emph{root Huffman tree} hingga sampai ke huruf yang ingin kita cari kode Huffman-nya. Sebagai contoh, untuk huruf $H$, kita pergi berawal dari \emph{root} ke anak kanan, lalu ke kiri, dan terakhir ke kanan sampai di verteks $H$, sehingga kita dapatkan kode Huffman untuk $H$ adalah $101$. Selengkapnya kode Huffman untuk masing-masing karakter pada contoh ini diberikan dengan cara sebagai berikut:
\begin{center}
	\small{
		\begin{tabular}{|c|c|c|c||c|c|c|c|}
			\hline
				Karakter & Frekuensi & Kode & Jumlah & Karakter & Frekuensi & Kode & Jumlah \\
					& & Biner & Bit & & & Biner & Bit \\
			\hline
				A & 12 & 011 & 3 & E & 30 & 11 & 2 \\
				B & 3 & 10010 & 5 & F & 10 & 010 & 3 \\
				C & 20 & 00 & 2 & G & 6 & 1000 & 4 \\
				D & 4 & 10011 & 5 & H & 15 & 101 & 3 \\
			\hline
		\end{tabular}
	}
\end{center}

Satu hal yang perlu kita kaji lebih jauh adalah efisiensi yang didapatkan jika kita menyimpan huruf-huruf pada contoh ini dengan kode Huffman dibandingkan dengan jika disimpan dengan kode ASCII.

Jika kita misalkan jumlah total kemunculan seluruh huruf adalah 100, maka masing-masing huruf menyumbang beberapa bit sesuai panjang bit untuk huruf tersebut sesuai kode Huffman-nya. Jika kita hitung, total jumlah bit yang diperlukan adalah:
\[
12 \times 3+3 \times 5+20 \times 2+4 \times 5+30 \times 2+10 \times 3+6 \times 4+15 \times 3 = 270 \mathrm{bit}
\]
Bila saja kumpulan karakter tersebut dikodekan dengan cara biasa, yaitu  menggunakan 3 bit per karakter (3 bit mampu merepresentasikan 8 hal yang berbeda), maka jumlah bit yang diperlukan adalah 300 bit, karena setiap huruf menyumbang 3 bit, sedangkan total huruf yang ada adalah 100 buah. Dengan demikian kita dapat hitung efisiensi yang didapatkan dengan menyimpan distribusi huruf ini dengan kode Huffman adalah: $\frac{300-270}{300} \times 100\%=10\%$.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{Huffman} $(C)$
	\COMMENT Array $C$ berisi sekumpulan karakter beserta dengan frekuensi kemunculannya
	\STATE $n \leftarrow \mathrm{len}(C)$
	\STATE $Q \leftarrow $\textsc{PriorityQ}$(C)$
	\FOR{\(i \leftarrow 1\) to \(n-1\)}
	  \STATE \(z \leftarrow \) \textsc{AllocateNode()}
	  \COMMENT Buat node baru \(z\)
	  \STATE \(x \leftarrow \) \textsc{ExtractMin} \((Q)\)
	  \STATE \(y \leftarrow \) \textsc{ExtractMin} \((Q)\)
	  \STATE \(z \cdot \mathrm{left} \leftarrow x\)
	  \STATE \(z \cdot \mathrm{right} \leftarrow y\)
	  \STATE \(z \cdot \mathrm{freq} \leftarrow x \cdot \mathrm{freq} + y\cdot \mathrm{freq}\)
	  \STATE \textsc{Enqueue} \((Q,z)\)
	  \COMMENT Sisipkan $z$ ke dalam \emph{priority queue} $Q$
	\ENDFOR
	\STATE return \textsc{ExtractMin} \((Q)\)
\end{algorithmic}
\caption{Algoritma Huffman.} \label{alg:huffman}
\end{algorithm}

Algoritma Huffman dalam bentuk pseudocode ditunjukkan dalam Algoritme~\ref{alg:huffman}. Dalam algoritme tersebut, digunakan sebuah struktur data \index{priority queue@\emph{priority queue}} \emph{priority queue}. Struktur data ini memiliki sifat FIFO seperti pada \emph{queue} biasa, di mana elemen-elemen disisipkan pada sisi \emph{rear} atau \emph{tail}, sedangkan proses pengambilan dilakukan dari sisi \emph{head} atau \emph{front}. Pada \emph{priority queue} sebuah elemen dijinkan untuk disisipkan di antara elemen-elemen yang sudah ada, tidak harus melalui sisi \emph{rear}. Artinya, sebuah elemen yang baru disisipkan boleh 'mendahului' elemen yang ada pada ujung paling belakang. Ijin ini diberikan jika elemen baru tersebut memiliki prioritas 'lebih tinggi' daripada elemen-elemen yang dia dahului. Dalam kasus \emph{Huffman code}, prioritas sebuah elemen ditentukan dari nilai frekuensi sebuah elemen atau verteks, atau bisa juga nilai frekuensi dari gabungan beberapa elemen huruf yang sudah membentuk sebuah \emph{tree}.


\subsection{Prefix Code} \label{sect:prefix-code}

Satu hal yang membuat \emph{Huffman Code} bermanfaat adalah bahwa tidak mungkin muncul kesalahan interpretasi ketika kita menerima urutan kode biner dalam kode \emph{Huffman}. Sifat semacam ini disebut sebagai sifat \index{prefix code@\emph{prefix code}} \emph{Prefix Code}.


\section{Latihan}

\begin{ExerciseList}
  \Exercise \label{ex:pekerjaan} Kecepatan pekerja A, B, C dan D dalam melakukan pekerjaan 1, 2, 3 dan 4 masing-masing adalah sebagai berikut:
  
  \begin{center}
		\begin{tabular}{|c|c|c|c|c|}
			\hline
					& Tugas 1 & Tugas 2 & Tugas 3 & Tugas 4 \\
			\hline
			\hline
				A & 9 & 2 & 7 & 8 \\
				B & 6 & 4 & 3 & 7 \\
				C & 5 & 8 & 1 & 8 \\
				D & 7 & 6 & 9 & 4 \\
			\hline
		\end{tabular}
  \end{center}
  
  Buatlah algoritma greedy untuk menetapkan tugas yang harus dikerjakan masing-masing pekerja.
  
  \Exercise Gambarkan graf berbobot yang anda gunakan dalam menjawab latihan Soal~\ref{ex:pekerjaan}.
  
  \Exercise Buktikan bahwa suatu graf berbobot terhubung yang setiap edgenya mempunyai bobot yang berbeda, hanya akan mempunyai satu \emph{minimum spanning tree}
  
  \Exercise \label{ex:find-mst} Dari graf pada Gambar~\ref{fig:ex:prim-kruskal}, carilah \emph{minimum spanning tree} dengan menggunakan algoritme Prim dan Kruskal. Pilih sembarang verteks sebagai \emph{source vertex} untuk algoritme Prim. Bandingkan hasil yang didapatkan oleh masing-masing algoritme.
  \begin{figure}
		\begin{center}
		  \resizebox*{0.7\textwidth}{!}{
				\includegraphics{graph-for-mst-1}
			}
			\caption{Minimum Spanning Tree} untuk Soal~\ref{ex:find-mst}. \label{fig:ex:prim-kruskal}
		\end{center}
	\end{figure}
	
	\Exercise Bila  \(G=(V,E)\) merupakan suatu graph tak terhubung, manakah diantara kedua algoritma tersebut yang dapat menghasilkan \index{minimum spanning tree@\emph{minimum spanning tree}!forest@\emph{forest}} \index{minimum spanning forest@\emph{minimum spanning forest}} \emph{minimum spanning forest} (\emph{forest} di mana setiap \emph{tree}-nya adalah \emph{minimum spanning tree}).
	
	\Exercise Dengan menggunakan pengetahuan dalam pencarian \emph{minimum spanning tree}, buatlah algoritma untuk mencari \emph{maximum spanning tree}.
	
	\Exercise Algoritme mana yang memiliki kompleksitas lebih rendah, Kruskal atau Prim? Dalam kondisi seperti apa algoritme Kruskal memiliki kompleksitas lebih rendah daripada algoritme Prim? Dalam kondisi seperti apa keadaan sebaliknya terjadi?
	
	\Exercise \label{ex:dijkstra} Carilah jarak terdekat verteks \(a\) terhadap setiap verteks lainnya pada graf dalam Gambar~\ref{fig:ex:dijkstra}.
	\begin{figure}
		\begin{center}
%			Place 2 rows of vertices: a and b; c, d, and f. Draw weighted directed edges from a to b (4); a to c (3); b to f (6); c to d (7); d to a (2); d to b (5); f to d (4).
      \includegraphics{graph-for-dijkstra-1}
		\end{center}
		\caption{Graf untuk Soal~\ref{ex:dijkstra}} \label{fig:ex:dijkstra}
	\end{figure}
	
	\Exercise \label{ex:dijkstra-negative-edge} Algoritme Dijkstra yang dibahas dalam buku ini menggunakan bobot tiap edge dengan nilai positif. Apa yang terjadi jika terdapat satu atau beberapa edge dalam sebuah graf yang bernilai negatif? Diskusikan dengan membuat sebuah graf sebagai contoh.
	
	\Exercise Jika dari sebuah graf berbobot sudah ditemukan MST-nya, apakah MST tersebut dapat digunakan untuk menjawab masalah \emph{single-source shortest-path}? Berikan alasannya.
	
	\Exercise \label{ex:graph-representation-incident} Sebuah graf dapat direpresentasikan dengan \emph{incidence list} atau \emph{incidency matrix}. Tidak seperti dalam representasi \emph{adjacent list} atau \emph{adjacency matrix}, representasi ini mencatat hubungan antara verteks dengan edge. Jumlah baris dalam representasi ini sesuai dengan jumlah verteks, sedangkan jumlah kolomnya sesuai dengan jumlah \emph{edge}. Jika sebuah edge ber-\emph{incident} dengan sebuah verteks, maka informasi tersebut dalam \emph{incidence list} atau \emph{incidency matrix}.
	
	Gambarkan graf~\ref{fig:ex:dijkstra} dengan menggunakan representasi \emph{incidence list} dan \emph{incidency matrix}.
	
	\Exercise Turunkan kompleksitas ruang yang digunakan oleh \emph{incidence list} dan \emph{incidency matrix}.
	
	Dalam situasi seperti apa \emph{incidence list} memiliki kompleksitas yang lebih unggul dibandingkan \emph{incidency matrix}? Bagaimana dengan sebaliknya?
	
	\Exercise \label{ex:dijkstra-implementation-adjacency} Implementasikan algoritma Dijkstra dengan beberapa struktur data graf yang dibahas (\emph{adjacency list} dan \emph{adjacency matrix}). Buat implementasi dengan menggunakan bahasa pemrograman favorit anda.
	
	\Exercise \label{ex:dijkstra-implementation-incidency} Implementasikan algoritma Dijkstra dengan struktur data graf \emph{incidence list} dan \emph{incidency matrix}.
	
	\Exercise \label{ex:graph-generator} Buatlah sebuah program yang secara acak membangkitkan graf dengan jumlah verteks tertentu. Program ini membuat sebuah graf dengan jumlah edge secara acak (mulai dari 0 sampai dengan jumlah maksimum edge yang mungkin dalam sebuah graf lengkap). Asumsikan graf yang dibangkitkan adalah graf simple. Simpan hasil graf yang dibangkitkan dengan menggunakan struktur data \emph{adjacency list}, \emph{adjacency matrix}, \emph{incidence list}, ma
	
	\Exercise Bandingkan \emph{running time} dari algoritma Dijkstra yang anda implementasikan dalam Soal~\ref{ex:dijkstra-implementation-adjacency} dan~\ref{ex:dijkstra-implementation-incidency} untuk berbagai macam graf yang berbeda-beda. Gunakan program pembangkit graf yang anda implementasikan pada Soal~\ref{ex:graph-generator}.
	
	\Exercise Berapakah tinggi maksimum suatu Huffman tree untuk mengkodekan $n$ buah karakter?
	
	\Exercise \label{ex:huffman} Suatu dokumen hanya terdiri dari karakter A, I, U, E dan O, dengan jumlah masing-masing karakter adalah 35\%, 10\%, 20\%, 20\% dan 15\% ingin dikirim melalui jaringan komputer. Berikanlah pengkodean untuk setiap karakter tersebut agar biaya pengiriman minimal.
	
	\Exercise Hitunglah kompleksitas algoritme Huffman jika diberikan masukan $n$ simbol berbeda dengan frekuensi kemunculan setiap simbol $p_{1}, p_{2}, \ldots p_{n}$.
	
	\Exercise Hitung efisiensi yang didapatkan dari pengkodean pada Soal~\ref{ex:huffman} dibandingkan jika huruf-huruf tersebut disimpan dengan kode ASCII-7 bit.
	
	\Exercise Bagaimana jika dalam penyusunan \emph{Huffman tree} didapatkan sebuah pasangan \emph{tree} atau verteks yang memiliki bobot yang sama?
	
	\Exercise Implementasikan algoritme Huffman dalam bentuk dua program. Program pertama menerima masukan berupa berkas teks atau sekumpulan berkas teks. Program ini membuat representasi Huffman dari simbol-simbol yang terdapat dalam berkas masukan, dan menuliskannya pada sebuah berkas tunggal.
	
	Program kedua menerima masukan sebuah berkas berisi representasi Huffman yang dihasilkan oleh program pertama. Program kedua harus dapat mengembalikan representasi berkas asli yang dikodekan oleh program pertama.
	
	Lakukanlah beberapa kali eksperimen untuk menghitung perbandingan jumlah simbol yang dikodekan dengan waktu yang dibutuhkan oleh program anda untuk menghasilkan representasi Huffman-nya. Lakukan juga eksperimen untuk menghitung perbandingan ukuran kode Huffman terhadap waktu yang dibutuhkan untuk mengembalikan representasi asli simbol-simbol.
\end{ExerciseList}
